package com.fw.leetcode.doublepointer;

import com.fw.leetcode.LeetCode;

/**
 * 165. Compare Version Numbers
 *
 * Given two version strings, version1 and version2, compare them. A version string consists of revisions separated by dots '.'.
 * The value of the revision is its integer conversion ignoring leading zeros.
 *
 * To compare version strings, compare their revision values in left-to-right order.
 * If one of the version strings has fewer revisions, treat the missing revision values as 0.
 *
 * Return the following:
 *  · If version1 < version2, return -1.
 *  · If version1 > version2, return 1.
 *  · Otherwise, return 0.
 *
 * Example 1:
 *  Input: version1 = "1.2", version2 = "1.10"
 *  Output: -1
 *  Explanation:
 *    version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.
 *
 * Example 2:
 *  Input: version1 = "1.01", version2 = "1.001"
 *  Output: 0
 *  Explanation:
 *    Ignoring leading zeroes, both "01" and "001" represent the same integer "1".
 *
 * Example 3:
 *  Input: version1 = "1.0", version2 = "1.0.0.0"
 *  Output: 0
 *  Explanation:
 *    version1 has less revisions, which means every missing revision are treated as "0".
 *
 * Constraints:
 *  1 <= version1.length, version2.length <= 500
 *  version1 and version2 only contain digits and '.'.
 *  version1 and version2 are valid version numbers.
 *  All the given revisions in version1 and version2 can be stored in a 32-bit integer.
 */
public class Num_0165 implements LeetCode {
    private interface Solution {
        int compareVersion(String version1, String version2);

        default void assertEquals(String version1, String version2, int expected) {
            if (compareVersion(version1, version2) != expected) {
                compareVersion(version1, version2);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public int compareVersion(String version1, String version2) { // 分割字符串+单指针：时O(n+m) 空O(<n+m)
            /*
             * 比较版本号
             * version1 = "1.2",   version2 = "1.10"     => -1
             * version1 = "1.01",  version2 = "1.001"    => 0
             * version1 = "1.0",   version2 = "1.0.0.0"  => 0
             */
            String[] vArr1 = version1.split("\\.");
            String[] vArr2 = version2.split("\\.");
            int idx = 0;
            while (idx < Math.max(vArr1.length, vArr2.length)) {
                int t1 = idx >= vArr1.length ? 0 : Integer.parseInt(vArr1[idx]);
                int t2 = idx >= vArr2.length ? 0 : Integer.parseInt(vArr2[idx]);
                if (t1 != t2) {
                    return Integer.compare(t1, t2);
                }
                idx++;
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertEquals("1.2", "1.10", -1);
        solution.assertEquals("1.01", "1.001", 0);
        solution.assertEquals("1.0", "1.0.0.0", 0);
    }
}
